# Definition for a binary tree node.
import collections
class TreeNode:
    def __init__(self, x):
        self.val = x
        self.left = None
        self.right = None

# class Solution:
#     def findMode(self, root):
#         """
#         :type root: TreeNode
#         :rtype: List[int]
#         """
#         if not root:
#             return []
#         if not root.left and not root.right:
#             return [root.val]
#         a=[]
#         m = self.middle(root,a)
#         index = 0
#         max = 0
#         b = []
#         for i in range(len(m)):
#             flag = 0
#             for j in range(i+1,len(m)):
#                 if m[i] == m[j]:
#                     flag+=1
#             if flag > max:
#                 max = flag
#                 # index = i
#                 b.append(m[i])
#         return b
#
#
#     def middle(self,root,a):
#         if root:
#             self.middle(root.left,a)
#             a.append(root.val)
#             self.middle(root.right,a)
#         return a
#
#
#
#     #
#     #     if not root:
#     #         return []
#     #     modes =[]
#     #     val,freq,max_freq,modes = self.dfs(root,None,0,0,modes)
#     #     return modes
#
#     # def dfs(self,node, val, freq, max_freq, modes):
#     #     if node.left:
#     #         val, freq, max_freq, modes = self.dfs(node.left, val, freq, max_freq, modes)
#     #     if node.val == val:
#     #         freq+=1
#     #     else:
#     #         freq = 1
#     #         val = node.val
#     #
#     #     if freq > max_freq:
#     #         modes=[val]
#     #         max_freq =freq
#     #     elif freq == max_freq:
#     #         modes.append(val)
#     #     if node.right:
#     #         val, freq, max_freq, modes = self.dfs(node.right, val, freq, max_freq, modes)
#     #
#     #     return val, freq, max_freq, modes

class Solution(object):
    def findMode(self, root):
        """
        :type root: TreeNode
        :rtype: List[int]
        """
        self.modes = []
        self.max_freq = 0
        self.cur_freq = 0
        self.cur_item = None
        if root:
            self.inorder(root)
        return self.modes

    def calc_freq(self, value):
        if self.cur_item == value:
            self.cur_freq += 1
        else:
            self.cur_item = value
            self.cur_freq = 1
        if self.cur_freq > self.max_freq:
            self.max_freq = self.cur_freq
            self.modes = [self.cur_item]
        elif self.cur_freq == self.max_freq:
            self.modes.append(value)

    def inorder(self, root):
        if root:
            self.inorder(root.left)
            self.calc_freq(root.val)
            self.inorder(root.right)


m1 = TreeNode(1)
# m1.left = TreeNode(0)
m1.right = TreeNode(2)
m1.right.left = TreeNode(2)
# m1.right.right = TreeNode(3)
s = Solution()

t = s.findMode(m1)
print(t)
